use std::collections::HashSet;

pub fn goldbach_conjecture() -> u64 {
    let mut primes = HashSet::new();
    primes.insert(2);

    let mut perfect_squares = vec![1];

    let mut first = None;

    let mut i = 0;
    loop {
        i += 1;
        let val = i * 2 + 3;
        while perfect_squares.last().unwrap() < &val {
            let length = perfect_squares.len() as u64 + 1;
            let val = length * length;
            perfect_squares.push(val);
        }

        if primes.iter().all(|x| val % x != 0) {
            primes.insert(val);
            continue;
        }

        let mut check = false;

        for &perfect_square in &perfect_squares {
            if val < 2 * perfect_square {
                break;
            }
            let sub = val - 2 * perfect_square;
            if primes.contains(&sub) {
                check = true;
                break;
            }
        }

        if !check {
            match first {
                Some(first) => return first + val,
                None => first = Some(val),
            }
        }
    }
}
